Grokking Meta Coding Interview
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Introduction
Who Should Take This Course?
Meta Easy Problems
Toeplitz Matrix (easy)
Solution: Toeplitz Matrix
Remove All Adjacent Duplicates In String (easy)
Solution: Remove All Adjacent Duplicates In String
Minimum Depth of a Binary Tree (easy)
Solution: Minimum Depth of a Binary Tree
Tree Diameter (easy)
Solution: Tree Diameter
Island Perimeter (easy)
Solution: Island Perimeter
Moving Average from Data Stream (easy)
Solution: Moving Average from Data Stream
Move Zeroes (easy)
Solution: Move Zeroes
Missing Ranges (easy)
Solution: Missing Ranges
Palindrome Permutation (easy)
Solution: Palindrome Permutation
Rank Transform of an Array (easy)
Solution: Rank Transform of an Array
Meta Medium Problems
Diagonal Traverse (medium)
Solution: Diagonal Traverse
Shortest Path in Binary Matrix (medium)
Solution: Shortest Path in Binary Matrix
Maximum Swap (medium)
Solution: Maximum Swap
Custom Sort String (medium)
Solution: Custom Sort String
Binary Tree Vertical Order Traversal (medium)
Solution: Binary Tree Vertical Order Traversal
Buildings With an Ocean View (medium)
Solution: Buildings With an Ocean View
Basic Calculator II (medium)
Solution: Basic Calculator II
Nested List Weight Sum (medium)
Solution: Nested List Weight Sum
Dot Product of Two Sparse Vectors (medium)
Solution: Dot Product of Two Sparse Vectors
Max Consecutive Ones III (medium)
Solution: Max Consecutive Ones III
Subarray Sum Equals K (medium)
Solution: Subarray Sum Equals K
Next Permutation (medium)
Solution: Next Permutation
Simplify Path (medium)
Solution: Simplify Path
Lowest Common Ancestor of a Binary Search Tree (medium)
Solution: Lowest Common Ancestor of a Binary Search Tree
'K' Closest Points to the Origin (medium)
Solution: 'K' Closest Points to the Origin
Sum of Path Numbers (medium)
Solution: Sum of Path Numbers
Merge Intervals (medium)
Solution: Merge Intervals
Right View of a Binary Tree (medium)
Solution: Right View of a Binary Tree
Number of Islands (medium)
Solution: Number of Islands
Clone Graph (medium)
Solution: Clone Graph
Missing Element in Sorted Array (medium)
Solution: Missing Element in Sorted Array
Number of Substrings Containing All Three Characters (medium)
Solution: Number of Substrings Containing All Three Characters
Capacity To Ship Packages Within D Days (medium)
Solution: Capacity To Ship Packages Within D Days
Count and Say (medium)
Solution: Count and Say
Contiguous Array (medium)
Solution: Contiguous Array
Sliding Window Median (hard)
Solution: Sliding Window Median
Alien Dictionary (hard)
Solution: Alien Dictionary
Minimum Window Substring (hard)
Solution: Minimum Window Substring
Best Meeting Point (hard)
Solution: Best Meeting Point
Maximum Sum of 3 Non-Overlapping Subarrays (hard)
Solution: Maximum Sum of 3 Non-Overlapping Subarrays
Making A Large Island (hard)
Solution: Making A Large Island
Basic Calculator (Hard)
Solution: Basic Calculator
Serialize and Deserialize Binary Tree (hard)
Solution: Serialize and Deserialize Binary Tree
Longest Increasing Path in a Matrix (hard)
Solution: Longest Increasing Path in a Matrix
Valid Palindrome III (hard)
Solution: Valid Palindrome III
Solution: Right View of a Binary Tree

Problem Statement

Given a root of the binary tree, return an array containing nodes in its right view.

The right view of a binary tree consists of nodes that are visible when the tree is viewed from the right side. For each level of the tree, the last node encountered in that level will be included in the right view.

Examples

Example 1

  • Input: root = [1, 2, 3, 4, 5, 6, 7]
Image
  • Expected Output: [1, 3, 7]
  • Justification:
    • The last node at level 0 is 1.
    • The last node at level 1 is 3.
    • The last node at level 2 is 7.

Example 2

  • Input: root = [12, 7, 1, null, 9, 10, 5, null, 3]
Image
  • Expected Output: [12, 1, 5, 3]
  • Justification:
    • The last node at level 0 is 12.
    • The last node at level 1 is 1.
    • The last node at level 2 is 5.
    • The last node at level 3 is 3.

Example 3

  • Input: root = [8, 4, 9, 3, null, null, 10, 2]
Image
  • Expected Output: [8, 9, 10, 2]
  • Justification:
    • The last node at level 0 is 8.
    • The last node at level 1 is 9.
    • The last node at level 2 is 10.
    • The last node at level 3 is 2.

Constraints:

  • The number of nodes in the tree is in the range [0, 100].
  • -100 <= Node.val <= 100

Solution

To solve this problem, we will use the Breadth-First Search (BFS) agorithm to traverse the binary tree and compute the right view of the tree. It processes the tree level by level, ensuring that at each level, the last node encountered (rightmost node) is stored in the result list. A queue is used to facilitate level-wise traversal, and at the end of each level, the last node is added to the result.

Step-by-Step Algorithm

  1. Base Case: If the root is null, return an empty list since there are no nodes to process.

  2. Initialize Queue: Create an empty queue and add the root node to it. This queue is used to traverse the tree level by level, starting from the root.

  3. While the Queue is Not Empty:

    • Determine Level Size: Calculate the number of nodes at the current level using queue.size(). This ensures that we process all nodes at the same level before moving to the next level.

    • Process Each Node at the Current Level:

      • For each node in the current level:
        • Dequeue the Current Node: Poll the node from the front of the queue.
        • Add its Left Child to the Queue: If the current node has a left child, add it to the queue to process in the next level.
        • Add its Right Child to the Queue: If the current node has a right child, add it to the queue for the next level.
    • Add the Last Node of the Level to the Result: After processing all nodes at the current level, add the value of the last node (rightmost node) to the result list. This node will represent the right view at that level.

  4. Repeat: Continue this process for each level until the queue is empty, meaning all levels have been processed.

  5. Return the Result: After processing all levels, the result list will contain the nodes visible from the right view of the tree.

Algorithm Walkthrough

Input: root = [12, 7, 1, null, 9, 10, 5, null, 3]

Image

Step-by-Step Execution

  1. Initialization:

    • The root node is 12. Add 12 to the queue.

    Queue: [12] Result: []

  2. Level 1:

    • queue.size() is 1, meaning there is 1 node at this level.
    • Dequeue node 12.
    • Add its left child (7) and right child (1) to the queue.
    • Add 12 in the result list.

    Queue: [7, 1] Result: [12]

  3. Level 2:

    • queue.size() is 2, meaning there are 2 nodes at this level.
    • Dequeue node 7. Add its right child (9) to the queue (it has no left child).
    • Dequeue node 1. Add its left child (10) and right child (5) to the queue.
    • Since 1 is the last node at this level, add it to the result.

    Queue: [9, 10, 5] Result: [12, 1]

  4. Level 3:

    • queue.size() is 3, meaning there are 3 nodes at this level.
    • Dequeue node 9. Add its right child (3) to the queue (it has no left child).
    • Dequeue node 10. It has no children.
    • Dequeue node 5. It has no children.
    • Since 5 is the last node at this level, add it to the result.

    Queue: [3] Result: [12, 1, 5]

  5. Level 4:

    • queue.size() is 1, meaning there is 1 node at this level.
    • Dequeue node 3. Since it's the only node at this level, add it to the result.
    • Node 3 has no children, so nothing is added to the queue.

    Queue: [] Result: [12, 1, 5, 3]

  6. Completion: The queue is now empty, meaning all levels of the tree have been processed. The right view of the tree is complete.

Final Output: [12, 1, 5, 3]

Code

Here is the code for this algorithm:

Java
Saved to Cloud

. . . .

Time Complexity

The time complexity of the above algorithm is , where ā€˜N’ is the total number of nodes in the tree. This is due to the fact that we traverse each node once.

Space Complexity

  • The space complexity of the above algorithm will be for the queue. Since we can have a maximum of N/2 nodes at any level (this could happen only at the lowest level), therefore we will need space to store them in the queue.
  • Also, we use space space for result list. For the skewed tree we need to store all N elements in the result list.

Similar Questions

Problem 1: Given a binary tree, return an array containing nodes in its left view. The left view of a binary tree is the set of nodes visible when the tree is seen from the left side.

Solution: We will be following a similar approach, but instead of appending the last element of each level, we will be appending the first element of each level to the output array.

Right View of a Binary Tree (medium)
Number of Islands (medium)
Mark as Completed

On this page

Problem Statement

Examples

Solution

Step-by-Step Algorithm

Algorithm Walkthrough

Code

Time Complexity

Space Complexity

Similar Questions